/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/02
 */
package CodingTest.AC20190402;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 请判断一个链表是否为回文链表。

 示例 1:

 输入: 1->2
 输出: false
 示例 2:

 输入: 1->2->2->1
 输出: true
 */
public class isPalindrome {
    class ListNode{
        int val;
        ListNode next;
        ListNode(int x){
            val = x;
        }
    }
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode prev = null;
        fast = slow;//fast指针用来记录中间节点的位置
        while(slow != null) {//反转链表的后半部分
            ListNode temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }
        while(prev!=null){
            if(head.val !=prev.val){
                return false;
            }
            head=head.next;
            prev = prev.next;
        }
        return true;

    }

}
